package cn.qyd.leecode;

/**
 * @author 邱运铎
 * leecode 928 减少恶意软件的传播 II
 * @date 2024-04-17 10:40
 */
public class BadNodeInfectII {
    private int infectNums;

    public static void main(String[] args) {
        BadNodeInfectII demo = new BadNodeInfectII();
        int[][] graph = new int[][]{{1,1,0},{1,1,0},{0,0,1}};
        int[] initial = new int[]{0, 1};
        int i = demo.minMalwareSpread(graph, initial);
        System.out.println(i);
    }
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        int removeNode = -1;
        int minFinalInfectNodes = n;
        int curInfectNodes;
        for (int initialBadNode : initial) {
            // remove initialBadNode
            // graph[initialBadNode] = {0,0,...0};
            // 获取剩余最初感染节点最终的感染节点数
            // 比较最终感染节点数，最终得到最小的感染节点数和节点id

            computeRemoveNodeInfect(initialBadNode, graph, initial);
            curInfectNodes = infectNums;
            System.out.println(initialBadNode);
            System.out.println(curInfectNodes);
            if (curInfectNodes < minFinalInfectNodes || (curInfectNodes == minFinalInfectNodes && initialBadNode < removeNode) ) {
                removeNode = initialBadNode;
                minFinalInfectNodes = curInfectNodes;
                System.out.println(removeNode);
                System.out.println(minFinalInfectNodes);
                System.out.println("------------");
            }
        }

        return removeNode;
    }

    public void computeRemoveNodeInfect(int node, int[][] graph, int[] initial) {
        infectNums = 0;
        boolean[] visited =new boolean[graph.length];
        for (int badNode : initial) {
            if (badNode == node) {
                continue;
            }
            if (!visited[badNode]) {
                dfs(graph, badNode,node,visited);
            }
        }
    }

    public void dfs(int[][] graph, int badNode, int originNode, boolean[] visited) {
        infectNums++;
        visited[badNode] = true;
        for (int i = 0; i < graph[badNode].length; i++) {
            if (!visited[i] && i != originNode && graph[badNode][i] == 1) {
                dfs(graph, i, originNode, visited);
            }
        }
    }
}
